package Graph;

import unionFindSet.UnionFindSet;

import java.util.*;

/**
 * 实现：邻接图的相关操作
 */
public class Graph {
    private static final int INF = (int) 1e9 + 7;

    // 记录顶点的下标
    Map<Character, Integer> vertex = null;
    // 邻接矩阵
    int[][] matrix = null;
    // 顶点的数目
    int size;
    // 是不是有向图
    boolean isDirect ;

    public Graph(int size, boolean isDirect) {
        this.size = size;
        this.isDirect = isDirect;

        vertex = new HashMap<>();
        matrix = new int[size][size];
        for (int[] cur : matrix) {
            Arrays.fill(cur, INF);
        }
    }

    // 初始化图
    public void initGraph(char[] vertex) {
        for (int i = 0; i < vertex.length; i ++) {
            this.vertex.put(vertex[i], i);
        }
    }

    // 根据下标增加一条边
    public void addEdgeByIndex(int srcIdx, int destIdx, int w) {
        matrix[srcIdx][destIdx] = w;
        // 如果是无向图
        if (!isDirect) {
            matrix[destIdx][srcIdx] = w;
        }
    }

    // 两个顶点之间添加一条边
    public void addEdge(char src, char dest, int w) {
        addEdgeByIndex(vertex.get(src), vertex.get(dest), w);
    }

    // 获取顶点下标
    public Integer getVertexIndex(char v) {
        return vertex.getOrDefault(v, 0);
    }

    // 获取顶点的度 -- 出度 + 入度
    public int getDev(char v) {
        int dev = 0;

        int idx = vertex.get(v); // 获取顶点下标
        // 获取出度
        for (int i = 0; i < size; i ++) {
            if (matrix[idx][i] != INF) {
                dev ++;
            }
        }

        if (isDirect) {
            // 获取入度
            for (int i = 0; i < size; i ++) {
                if (matrix[i][idx] != INF) {
                    dev ++;
                }
            }
        }
        return dev;
    }

    // 广度优先遍历图
    // 弹出 和 入队 都要标记为 TRUE
    public void bfs(char start) {
        int startIdx = vertex.get(start);
        boolean[] visited = new boolean[size];
        Queue<Integer> que = new LinkedList<>();
        que.offer(startIdx);

        while (!que.isEmpty()) {
            int p = que.poll();
            visited[p] = true;
            System.out.println(p + " ");

            for (int i = 0; i < size; i ++) {
                if (matrix[p][i] != INF && !visited[i]) {
                    que.offer(i);
                    visited[i] = true;
                }
            }
        }
    }

    // 深度优先遍历
    public void dfs(char v) {
        int idx = getVertexIndex(v);
        bfsChild(idx, new boolean[size]);
    }

    private void bfsChild(int idx, boolean[] visited) {
        visited[idx] = true;
        System.out.println(idx);

        for (int i = 0; i < size; i ++) {
            if (matrix[idx][i] != INF && !visited[i]) {
                bfsChild(i, visited);
            }
        }
    }

    public static class Edge {
        int src ; // 起点
        int dest ; // 终点
        int w;   // 权值

        public Edge(int src, int dest, int w) {
            this.src = src;
            this.dest = dest;
            this.w = w;
        }
    }

    /**
     * 使用克鲁斯卡尔算法生成最小生成树
     * 思想: 贪心思想, 通过全局最优算法, 每次选取所有边中的最小边
     * @param minTree 输出型参数,
     * @return 返回最小生成树的权值
     */
    public int kruskal(Graph minTree) {
        // 最小堆, 每次提供一个最小权值边
        PriorityQueue<Edge> minHeap = new PriorityQueue<>((Edge o1, Edge o2) -> {return o1.w - o2.w;});
        // 添加所有边
        for (int i = 0; i < size; i ++) {
            for (int j = i; j < size; j ++) {
                if (matrix[i][j] != INF) {
                    minHeap.offer(new Edge(i, j, matrix[i][j]));
                }
            }
        }

        // 每次选最小的边
        UnionFindSet ufs = new UnionFindSet(size); // 并查集, 防止成环

        int totalWeight = 0; // 最小权值
        int count = 0; // 边的数量
        while (count < size - 1 && !minHeap.isEmpty()) { // 边数应该是 n - 1
            Edge p = minHeap.poll();
            int srcIdx = p.src, destIdx = p.dest, w = p.w;
            // 如果没连接起来前就是一个集合的
            if (!ufs.isConnected(srcIdx, destIdx)) {
                ufs.unit(srcIdx, destIdx);
                // 新增一个边
                minTree.addEdgeByIndex(srcIdx, destIdx, w);
                totalWeight += w;
                count ++;
            }
        }

        // 出了循环再判断一次, 如果边数 = 点数 - 1, 就完成了最小生成树
        if (count == size - 1) {
            return totalWeight;
        } else {
            return - 1;
        }
    }

    /**
     * 使用普利姆算法生成最小生成树, 选择一个点为起点
     * 思想: 局部最优, 每次选取这个点连接的最小权值边
     * @param minTree 生成最小生成树
     * @return 返回最小生成树的权值
     */
    public int prime(Graph minTree, char startVertex) {
        int startIdx = getVertexIndex(startVertex);

        // 需要定义两个集合, 一个是 已选 集合, 另一个是 未选 集合
        Set<Integer> choosed = new HashSet<>();
        Set<Integer> notChoosed = new HashSet<>();

        choosed.add(startIdx);
        for (int i = 0; i < size; i ++)
            if (i != startIdx)
                notChoosed.add(i);

        PriorityQueue<Edge> minHeap = new PriorityQueue<>((Edge o1, Edge o2) -> {return o1.w - o2.w;});
        for (int i = 0; i < size; i ++) {
            if (matrix[startIdx][i] != INF) {
                minHeap.offer(new Edge(startIdx, i, matrix[startIdx][i]));
            }
        }

        int count = 0; // 边的条数
        int totalWeight = 0; // 最小权值

        while (!minHeap.isEmpty()) {
            Edge p = minHeap.poll();
            int srcIdx = p.src, destIdx = p.dest, w = p.w;

            // destIdx 还没选择, 才能参与选择, 否则会成环
            if (!choosed.contains(destIdx)) {
                minTree.addEdgeByIndex(srcIdx, destIdx, w);
                totalWeight += w;
                count ++;

                if (count == size - 1) {
                    return totalWeight;
                }

                choosed.add(destIdx);
                notChoosed.remove(destIdx);
                for (int i = 0; i < size; i ++) {
                    // 下次选择的边也都不能包含已经选的
                    if (matrix[destIdx][i] != INF && !choosed.contains(i)) {
                        minHeap.offer(new Edge(destIdx, i, matrix[destIdx][i]));
                    }
                }
            }
        }

        return -1;
    }

    /**
     * 迪杰斯特拉算法, 用于求解单源最短路径
     * 缺点就是无法求解权值为负的图
     * @param startVertex 起点
     * @param dist 起到到某个点的最短距离数组
     * @param path 记录最短距离的编号
     */
    public void dijkstra(char startVertex, int[] dist, int[] path) {
        int start = getVertexIndex(startVertex);

        // 判断某个点是否已经被选入集合中
        boolean[] hasChoosed = new boolean[size];

        // 距离数组初始化为无限大
        Arrays.fill(dist, INF);
        dist[start] = 0; // 此处定义为 0, 为了第一轮查找能够找到目标

        Arrays.fill(path, -1);
        // path[start] = 0; // 这里应该没有也行

        // 要进行 n 条边次 循环
        // 内部还有两个循环, 第一个用于选取下一个点, 第二个用于利用选取后的点进行松弛
        for (int k = 0; k < size; k ++) {
            // 选中一条最短的路径
            int min = INF;
            int u = start; // 记录下一个要选取的点的下标
            for (int i = 0; i < size; i ++) {
                // 如果这个点还没选入集合中 并且 可以是最短的边值
                if (!hasChoosed[i] && dist[i] < min) {
                    min = dist[i];
                    u = i;
                }
            }
            hasChoosed[u] = true; // 选入集合中

            // 再以该点为基础, 松弛这个点连接的边
            for (int v = 0; v < size; v ++) {
                // 如果还没选入结合中 && 存在这个边 && 存在更短的路径
                if (!hasChoosed[v] && matrix[u][v] != INF && dist[u] + matrix[u][v] < dist[v]) {
                    dist[v] = dist[u] + matrix[u][v];
                    path[v] = u;
                }
            }
        }
    }

    // 以 startVertex 为起点, searchVertex 为终点
    // 返回 searchVertex 为终点最短路径
    public ArrayList<Integer> getShortestPath(int[] path, char startVertex, char searchVertex) {
        ArrayList<Integer> ret = new ArrayList<> ();
        int srcIdx = getVertexIndex(startVertex);
        int curIdx = getVertexIndex(searchVertex);
        ret.add(curIdx);

        while (curIdx != srcIdx) {
            curIdx = path[curIdx];
            ret.add(curIdx);
        }
        Collections.reverse(ret);
        return ret;
    }
}

